package LeetCode.RadixSort;

import java.util.Arrays;

/**
 * @author : LdLtd
 * @Date : 2023/9/12
 * @Description:堆排序
 */
public class RadixSort {
    public static void main(String[] args) {
        int[] arr = new int[] { 123, 55, 451, 313, 22, 0, 145, 2213, 6456, 104, 20, 15, 29, 48 };
        radixSort(arr);
        System.out.println(Arrays.toString(arr));
    }

    private static void radixSort(int[] arr) {
        // 存储数组中的最大数字
        int max = Integer.MIN_VALUE;//将max值初始为Integer类型的最小值
        //遍历数组,把最大值赋给max
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] > max)
                max = arr[i];
        }
        // 所有数字先加上一个最大数字的绝对数,保证整个数组都是>=0
        // 计算数字是几位数
        int maxlength = (max + "").length();//(max+"")将最大值转换成String类型,再得到它的长度
        // 用于临时存储数据的数组(二维数组)
        int[][] temp = new int[10][arr.length];
        // 根据最大长度来决定比较次数
        for (int i = 0, n = 1; i < maxlength; i++, n *= 10) {
            int[] count = new int[10];
            // 把每一个数字分别计算余数
            for (int j = 0; j < arr.length; j++) {
                int yushu = arr[j] / n % 10;
                temp[yushu][count[yushu]++] = arr[j];
            }
            //记录取的元素需要放的位置
            int index = 0;
            //把数字取出来
            for(int k = 0;k<count.length;k++) {
                //记录数量的数组中,若不为0才取
                if(count[k]!=0) {
                    //取出元素
                    for(int l = 0;l<count[k];l++) {
                        arr[index++]=temp[k][l];
                    }
                    count[k]=0;
                }
            }
        }
    }
}
